package SubjectTree.One;

import java.util.Deque;
import java.util.LinkedList;

import Utility.TreeNode;

public class InvertTree {

/**
 * 难度：简单
 * 
 * 226. 翻转二叉树
 * 	翻转一棵二叉树。
 * 
 * 示例：
 * 	输入：
 * 	     4
 * 	   /   \
 * 	  2     7
 * 	 / \   / \
 * 	1   3 6   9
 * 	输出：
 * 	     4
 * 	   /   \
 * 	  7     2
 * 	 / \   / \
 * 	9   6 3   1
 * 	
 * 备注:
 * 	这个问题是受到 Max Howell 的 原问题 启发的 ：
 * 	谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
 * 
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		InvertTree it = new InvertTree();
		System.out.println(it.invertTree1(TreeNode.MkTree("[4,2,7,1,3,6,9]")));
	}
	//自己写（前序遍历）
	public TreeNode invertTree(TreeNode root) {
		if(root==null)return root;
		Deque<TreeNode> deque = new LinkedList<>();
		TreeNode node = root;
		while(node!=null||!deque.isEmpty()) {
			while(node!=null) {
				
				TreeNode temp = node.left;
				node.left = node.right;
				node.right = temp;
				
				deque.push(node);
				node = node.left;
			}
			node = deque.pop();
			node = node.right;
		}
		return root;
    }
	//自己写（逐行遍历）
	public TreeNode invertTree1(TreeNode root) {
		if(root==null)return root;
		Deque<TreeNode> deque = new LinkedList<>();
		deque.offer(root);
		while(!deque.isEmpty()) {
			int currentLevelSize = deque.size();
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = deque.poll();
				if(node!=null) {
					TreeNode temp = node.left;
					node.left = node.right;
					node.right = temp;
				}
				if(node.right!=null)deque.offer(node.right);
				if(node.left!=null)deque.offer(node.left);
			}
		}
		return root;
    }
	//方法一：递归
	public TreeNode invertTree2(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree1(root.left);
        TreeNode right = invertTree1(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
